Several compilation systems for programming languages in the Scheme/Lisp family of programming languages convert a source program into a representation known as continuation-passing style, or CPS, in order to analyze and optimize the program being compiled. CPS represents the program as a particular organization of lambda expressions. CPS representation makes flow-of-control information explicit through the use of continuations. Although continuations are formally functions, they differ from non-continuation lambda expressions (NCLEs) in that they do not themselves have continuation arguments. Except in special cases, NCLEs must be able to "return" to their callers by invoking a continuation argument; typically this is realized by generating a call instruction when invoking the NCLE. Continuation functions, on the other hand, can always be invoked with just a branch instruction.
For an explanation in detail of standard CPS conversion, as well as a description of example algorithms, reference is made to "Rabbit: A Compiler For Scheme" by Steele, published in MIT Artificial Intelligence Laboratory Technical Report 474, May 1978 (especially pp. 56-59); and "Orbit: An Optimizing Compiler For Scheme," by Kranz, YALEU/DCS/RR-632, Feb. 1988 (especially pp. 20-26) available from the Yale University Library, the contents of which publications are herein incorporated by reference. For further background, see also "Compiling With Continuations" by Appel, publ. 1992 by Cambridge University Press.
To summarize briefly, CPS conversion makes continuations explicit by transforming the program to continuation-passing style. Each source language lambda expression is given an additional formal parameter bound to a continuation to be invoked with the result of executing the body. Each call is provided with a corresponding extra argument, the continuation to the call. An intermediate node tree known as the CPS tree is produced.
More specifically, the transformation or conversion consists of adding an extra argument, a continuation, to each combination. Each lambda expression is similarly changed by introducing an extra formal parameter to correspond to the continuation it will be passed. After the transformation, the notions of procedure call and return have been unified; i.e., procedures no longer return. Instead, a procedure does a computation and calls its continuation with the result of the computation as argument.
A typical standard CPS compiler distinguishes between lambda expressions which are continuations and those which are not continuations and processes them differently.
Scheme and related programming languages use recursion in the source language to express iteration. A typical standard CPS compiler detects these "tail recursion loops", and uses a different code generation algorithm for loop functions than for non-loop functions.